//
// Created by lenovo on 2023/12/19.
//

#ifndef SORT_MERGESORT_H
#define SORT_MERGESORT_H

#include <vector>
using namespace std ;

template <typename T>
void merge(vector<T>& src , int left , int mid , int right){
    vector<T> tmp (right - left + 1 );
    int i = left , j = mid + 1 , k = 0 ;
    //按顺序进入tmp
    while (i <= mid and j <= right){
        if (src[i] < src[j]){
            tmp[k ++] = src[i ++ ];
        }else{
            tmp[k ++ ] = src[j ++ ] ;
        }
    }
    //剩余元素进入tmp
    while (i <= mid){
        tmp[k ++] = src[i ++];
    }
    while( j <= right ){
        tmp[k ++] = src[j ++];
    }

    //将对应位置复制回去
    for (k = 0 ; k < tmp.size() ; k ++){
        src[left + k] = tmp[k] ;
    }
}

template <typename T>
void mergeSort(vector<T>& src , int left , int right){
    if (left >= right){
        return ;
    }
    int mid = (left + right) / 2 ;
    mergeSort(src , left , mid);
    mergeSort(src , mid + 1 , right);
    merge(src , left , mid , right);
}


#endif //SORT_MERGESORT_H
